Выражение НОД через исходные многочлены

Пусть даны ненулевые многочлены $f$ и $g$. Без ограничения общности, $\deg f > \deg g$. 1. Если $g \mid f$, то $\text{НОД}(f, g) = g$. 2. Если $g \nmid f$, разделим $f$ на $g$ с остатком: $f = q_1g + r_1$ 3. Если $r_1 \mid g$, процесс завершён. Иначе разделим $g$ на $r_1$ с остатком: $g = q_2r_1 + r_2$ 4. Если $r_2 \mid r_1$, процесс завершён. Иначе: $r_1 = q_3r_2 + r_3$ Продолжаем процесс, пока один из остатков не разделится на следующий. Последний ненулевой остаток равен $\text{НОД}(f, g)$.

Для ненулевых $f, g \in F[x]$, алгоритм Евклида завершается, и последний ненулевой остаток $r_n$ равен $\operatorname{НОД}(f, g)$

Процесс конечен, так как последовательность степеней остатков $\deg g > \deg r_1 > \deg r_2 > \dots \ge 0$ строго убывает. Рассмотрим шаги алгоритма: $$ \begin{align*} f &= q_1 g + r_1 \\ g &= q_2 r_1 + r_2 \\ &\dots \\ r_{n-2} &= q_n r_{n-1} + r_n \\ r_{n-1} &= q_{n+1} r_n \end{align*} $$ Из последнего равенства $r_n \mid r_{n-1}$, последовательно поднимаясь вверх получаем: $$\begin{align} r_{n} &\mid r_{n-2} \\ r_{n} &\mid r_{n-3} \\ \dots&\dots\dots \\ r_{n} &\mid g \\ r_{n} &\mid f \end{align}$$ Таким образом, $r_n$ — общий делитель $f, g$. Пусть $d$ — любой общий делитель $f, g$. Из первого равенства $d \mid r_1$. Спускаясь по равенствам, последовательно получаем $d \mid r_2, \dots, d \mid r_n$. Следовательно, $r_n$ — наибольший общий делитель. $\square$

Для любых ненулевых $f$ и $g$, используя алгоритм Евклида, можно выразить $\operatorname{НОД}(f, g)$ как: $$\operatorname{НОД}(f, g) = uf + vg$$

Вновь рассмотрим шаги алгоритма: $$\begin{align*} f &= q_1 g + r_1 \\ g &= q_2 r_1 + r_2 \\ &\dots \\ r_{n-3} &= q_{n-1} r_{n-2} + r_{n-1} \\ r_{n-2} &= q_n r_{n-1} + r_n \\ r_{n-1} &= q_{n+1} r_n \end{align*}$$ Выразим $r_{n} = \operatorname{НОД}(f, g)$ из предпоследней строки и $r_{n-1}$ из строки выше: $$\begin{align} r_{n} &= r_{n-2} - q_{n}r_{n-1} \\ r_{n-1} &= r_{n-3} - q_{n-1}r_{n-2} \end{align}$$ Подставив вторую строку в первую, получим: $$\begin{align} r_{n} &= r_{n-2} - q_{n}r_{n-1} \\ r_{n} &= r_{n-2} - q_{n}(r_{n-3} - q_{n-1}r_{n-2}) = (1 + q_{n-1}q_{n})r_{n-2} - q_{n}r_{n-3} \end{align}$$ Значит мы получили выражение через $r_{n-2}$ и $r_{n-3}$. Продолжая процесс и поднимаясь вверх, получим: $$\operatorname{НОД}(f, g) = r_{n} = uf + vg$$ $\square$